package J20250121_Dynamic;

/**
 * Created with IntelliJ IDEA.
 * Description: 动态规划59——60
 * User: 王圆豪
 * Date: 2025-02-19
 * Time: 22:57
 */

public class Solution10 {
    //组合总数IV——https://leetcode.cn/problems/combination-sum-iv/
    public int combinationSum4(int[] nums, int target) {
        int n = nums.length;
        int[] dp = new int[target+1];
        dp[0] = 1;
        for(int j = 1; j <= target; j++){
            for(int i = 0; i < n; i++){
                if(j >= nums[i]) dp[j] += dp[j-nums[i]];
            }
        }
        return dp[target];
    }

    //不同的⼆叉搜索树——https://leetcode.cn/problems/unique-binary-search-trees/
    public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= i; j++){
                dp[i] += dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }
}
